package SortAlgorithm;

import com.alibaba.fastjson.JSON;

import java.util.Arrays;

public class 希尔排序 implements ISort{

    /**
     * 是直接插入排序算法的一种更高效的改进版本;
     * 将整个数组分成一组组,组组之间进行插入排序,最后会分成最细的组,再依依排序,得出最终结果。
     */

    @Override
    public int[] sort(int[] arr) {
        return shellSort(arr);
    }

    public int[] shellSort(int[] arr){

        int gap=arr.length/2;

        while (gap>0){
            // 0 1 2 3 4 5 6 gap=3 奇数四组 [0,3] [1,4] [2,5] [3,6] 两两交换排序
            for (int i = gap; i < arr.length; i++) {
                int temp=arr[i];
                int preIndex=i-gap;
                //while里必须要temp,不然swap交换时会交换到i
                while (preIndex>=0&&arr[preIndex]>temp){
                    swap(arr,preIndex,preIndex+gap);//交换
                    preIndex-=gap;
                }
            }
            gap/=2;
        }

        return arr;
    }

    private void swap(int[] arr,int index1,int index2){
        int temp=arr[index1];
        arr[index1]=arr[index2];
        arr[index2]=temp;
    }

    public static void main(String[] args) {
        希尔排序 n=new 希尔排序();
        int[] arr={4,2,3,4,5,6,1,2,4,3,5,1,5,2,5,6,1,2};
        int[] result = n.shellSort(arr);
        System.out.println(JSON.toJSONString(result));
        Arrays.sort(arr);
        System.out.println(JSON.toJSONString(arr));
    }

}
